package org.zn.note.jdk.others;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * Created by zn on 2018/10/24.
 */
public class Search {

    public static void main(String[] args) {
        int size = 5000;
        int dest = size;

//        List linkedList = initList(size, new LinkedList());                   // 13373 毫秒（1千万数据）
//        testSearch(new BaseSearcher("BaseSearcher"), linkedList, dest);     //   128 毫秒（1千万数据）
//        testSearch(new BinarySearcher("BinarySearcher"), linkedList, dest); //    99 毫秒（1千万数据）

        List arrayList = initList(size, new ArrayList());                     //  1031 毫秒（1千万数据）
        testSearch(new BaseSearcher("BaseSearcher"), arrayList, dest);      //    35 毫秒（1千万数据）
        testSearch(new BinarySearcher("BinarySearcher"), arrayList, dest);  //     0 毫秒（1千万数据）
    }

    private static List initList(int number, List l) {
        long startTime = System.currentTimeMillis();
        for (int i = 1; i <= number; i++)
            l.add(i);
        System.out.println("initList time[" + (System.currentTimeMillis() - startTime) + "]");
        return l;
    }

    private static void testSearch(Searcher s, List l, int dest) {
        long startTime = System.currentTimeMillis();
        int i = s.search(l, dest);
        if (i == dest)
            System.out.println(s.getName() + ", time[" + (System.currentTimeMillis() - startTime) + "]");
        else
            System.out.println(s.getName() + " not found !");
    }
}

/**
 * 顺序查找：时间复杂度 O(N)  随着问题规模的变大（N↑），时间增加是线性的（增速快）。
 * 最坏情况：N=10，执行10次；N=1亿，执行1亿次；
 * 二分查找：时间复杂度 log2(底)N --> O(logN)  随着问题规模的变大（N↑），时间增加的很少。
 * 最坏情况：N=10，执行约4次（N <= 2的4次方）; N=1亿，执行约27次 （N <= 2的27次方）; 时间增速几乎可以忽略不计
 * <p>
 * 顺序查找的元素不需要是有序的，但是二分查找的元素需要是有序的！
 */
interface Searcher {

    String getName();

    int search(List l, int dest);
}

/* 顺序遍历查找 */
class BaseSearcher implements Searcher {

    private String name;

    BaseSearcher(String name) {
        this.name = name;
    }

    @Override
    public String getName() {
        return name;
    }

    @Override
    public int search(List l, int dest) {
        int returnCode = -1;
        Iterator it = l.iterator();
        while (it.hasNext()) {
            int value = (int) it.next();
            if (dest == value) {
                returnCode = value;
                break;
            }
        }
        return returnCode;
    }
}

/* 二分查找 */
class BinarySearcher implements Searcher {

    private String name;

    BinarySearcher(String name) {
        this.name = name;
    }

    @Override
    public String getName() {
        return name;
    }

    @Override
    public int search(List l, int dest) {
//        return search1(l, dest, 0, l.size() - 1);
        int index = Collections.binarySearch(l, dest);
        return (int)l.get(index);
    }

    /* 递归实现 */
    private int search0(List l, int dest, int begin, int end) {
        System.out.println("BinarySearcher: 递归实现");
        int returnCode = -1;
        int middlePosition = (end - begin) / 2 + begin;
        int value = (int) l.get(middlePosition);
        if (dest > value) {
            returnCode = search0(l, dest, middlePosition + 1, end);
        } else if (dest < value) {
            returnCode = search0(l, dest, begin, middlePosition - 1);
        } else {
            returnCode = value;
        }
        return returnCode;
    }

    // 其实递归的都可以用循环实现
    // 递归优点：说是递归更容易理解（我倒是觉得循环更容易理解）
    // 递归缺点：如果递归比较深，调用栈也是占内存的
    // 共同点：① 想法将问题的规模逐步缩小  ② 直到缩小到满足基线(标准)
    // 需要注意：如果问题是逐步扩大的，或者没有基线（退出条件），就是死循环或者死递归了
    /* 循环实现 */
    private int search1(List l, int dest, int begin, int end) {
        System.out.println("BinarySearcher: 循环实现");
        int middlePosition = 0;
        int min = (int) l.get(begin);
        int max = (int) l.get(end);
        if (dest < min || dest > max)
            return -1;
        while (true) {
            middlePosition = (end - begin) / 2 + begin;
            int value = (int) l.get(middlePosition);
            if (dest > value) {
                begin = middlePosition + 1;
            } else if (dest < value) {
                end = middlePosition - 1;
            } else {
                return value;
            }
        }
    }
}